home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2662 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: cymbal.aix.calpoly.edu!not-for-mail
  2. From: dstubbs@cymbal.aix.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: 22 Jan 1996 16:34:19 -0800
  6. Organization: California Polytechnic State University, San Luis Obispo
  7. Message-ID: <4e1aeb$1gl8@cymbal.aix.calpoly.edu>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>
  9. NNTP-Posting-User: dstubbs@cymbal.aix.calpoly.edu
  10.  
  11. In article <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>,
  12. Bill Simpson  <wsimpson@uwinnipeg.ca> wrote:
  13.  
  14. >Is there a fast way to decide whether a number n is a power of 2?
  15.  
  16.    --[text deleted]
  17. >
  18. >Bill Simpson
  19.  
  20. There have been many responces to this post. I have selected four
  21. approaches to solving this problem and implemented them using
  22. a "common" coding approach. I timed these implementations by
  23.                               ^^^^^
  24. measuring the time to search the first 500,000 integers for
  25. powers of two. I performed these measurements on four different
  26. combinations of compiler/hardware. The four times (normalized)
  27. are shown as a comment with each of the implementations. In each
  28. case the compiler was to its highest optimization level.
  29. (The times are normalized with respect to each of the four
  30.  compiler/hardware combinations.)
  31.  
  32. Here are four of the approaches that were posted--along with
  33. the results of a few simple timing studies.
  34.  
  35.      Implementation                Normalized Execution Times
  36.     ----------------              ----------------------------
  37.  
  38. int is_power_of_two(int k) {       /* 1.0  1.0  1.0  1.0 */
  39.    if (k <= 0) return 0;
  40.    return (!(k & (k-1)));
  41. }
  42.  
  43. int is_power_of_two(int k) {       /*  1.1  1.0  1.1  1.0 */
  44.    if (k <= 0) return 0;
  45.    return ((k & (k-1))  == 0);
  46. }
  47.  
  48. int is_power_of_two(int k) {       /*  1.9  1.4  1.5  1.3 */
  49.     if (k <= 0) return 0;
  50.     while (k > 0) {
  51.         if (k & 1)
  52.          return (k > 1) ? 0 : 1;
  53.         k >>= 1;
  54.     }
  55. }
  56.  
  57. int is_power_of_two(int k) {       /* 7.1  5.8  5.1  3.6 */
  58.    int j;
  59.    if (k<=0) return 0;
  60.    for (j=0; k; k >>= 1)
  61.       if (k&1) ++j;
  62.    return (j == 1) ? 1 : 0;
  63. }
  64.  
  65.